package _mst;

/**
 * 面试题 01.05. 一次编辑
 */
public class T0105 {
    private String first, second;

    public boolean oneEditAway(String first, String second) {
        this.first = first;
        this.second = second;
        return dfs(first.length() - 1, second.length() - 1, 1);
    }

    private boolean dfs(int i, int j, int k) {
        if (k < 0) return false;
        else if (i < 0) return j < k;
        else if (j < 0) return i < k;
        else if (first.charAt(i) == second.charAt(j)) return dfs(i - 1, j - 1, k);
        else return dfs(i - 1, j, k - 1) || dfs(i, j - 1, k - 1) || dfs(i - 1, j - 1, k - 1);
    }
}
